1. Field of the Invention
The present invention relates to a data processing apparatus configured to execute call and return instructions, and to generate return address predictions for identified return instructions with reference to a return address stack.
2. Background
It is known for a data processing apparatus to execute program instructions which comprise both call and return instructions, wherein a call instruction causes the data processing apparatus to depart from sequential program instruction execution to execute a further sequence of program instructions until a return instruction is encountered when the data processing apparatus then returns to the original sequential program instruction flow following the call instruction which caused the departure. Such a data processing apparatus may be provided with a branch prediction unit which is configured to generate a return address prediction for an identified return instruction in the sequence of program instructions being executed, such that the data processing apparatus can already begin fetching the expected sequence of program instructions after that return instruction and passing them to the execution pipeline before that return instruction is actually executed, to avoid delays associated with the instruction fetching and pipelining process.
The return address prediction may be generated on the basis of the content of a return address stack which the data processing apparatus maintains for this purpose. A return address is pushed onto the return address stack when a call instruction is executed (this return address typically being the address of the instruction sequentially following the call instruction) and for each return instruction which is executed, a return address is popped from the top of the return address stack. The content of the return address stack, in particular the return address on top of the return address stack, can then be used to provide a prediction of the return address.
This hardware-based mechanism for generating return address predictions is however reliant on the software written for the data processing apparatus adhering to an expected structure, in particular that call and return instructions in the program flow are logically paired. When this is not the case, i.e. when there is a broken call-return flow in the software, the functionality of the return address stack breaks down. Previously this would have been addressed by seeking to improve the software or the compilers.
In the case of a data processing apparatus configured to perform speculative instruction execution, various mechanisms have been implemented to respond to speculation errors, yet these do not address the issue of a broken call-return flow. These are: “Improving Prediction for Procedure Returns with Return-Address-Stack Repair Mechanisms”, Skadron, K. and Ahuja, P. S. and Martonosi, M. and Clark, D. W. —Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture—1998; “Mechanism for return stack and branch history corrections under misprediction in deep pipeline design”, Chiu, G. Y. and Yang, H. C. and Li, W. Y. H. and Chung, C. P. —Computer Systems Architecture Conference, 2008. ACSAC 2008. 13th Asia-Pacific—2008; and “Correct alignment of a return-address-stack after call and return mispredictions”, Desmet, V. and Sazeides, Y. and Kourouyiannis, C. and De Bosschere, K. —Workshop on Duplicating, Deconstructing and Debunking—2005.